/*
 * re_*exec and friends - 匹配正则表达式
 *
 * Copyright (c) 1998, 1999 Henry Spencer.  All rights reserved.
 *
 * Development of this software was funded, in part, by Cray Research Inc.,
 * UUNET Communications Services Inc., Sun Microsystems Inc., and Scriptics
 * Corporation, none of whom are responsible for the results.  The author
 * thanks all of them.
 *
 * Redistribution and use in source and binary forms -- with or without
 * modification -- are permitted for any purpose, provided that
 * redistributions in source form retain this entire copyright notice and
 * indicate the origin and nature of any modifications.
 *
 * I'd appreciate being given credit for this package in the documentation
 * of software which uses it, but that is not a requirement.
 *
 * THIS SOFTWARE IS PROVIDED ``AS IS'' AND ANY EXPRESS OR IMPLIED WARRANTIES,
 * INCLUDING, BUT NOT LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY
 * AND FITNESS FOR A PARTICULAR PURPOSE ARE DISCLAIMED.  IN NO EVENT SHALL
 * HENRY SPENCER BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL,
 * EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED TO,
 * PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA, OR PROFITS;
 * OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY,
 * WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR
 * OTHERWISE) ARISING IN ANY WAY OUT OF THE USE OF THIS SOFTWARE, EVEN IF
 * ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
 *
 * src/backend/regex/regexec.c
 *
 */

#include "regex/regguts.h"



/* 懒惰DFA表示 */
struct arcp
{								/* “指针”指向出弧 */
	struct sset *ss;
	color		co;
};

struct sset
{								/* 状态集 */
	unsigned   *states;			/* 指向位向量的指针 */
	unsigned	hash;			/* 位向量的哈希值 */
#define  HASH(bv, nw)	 (((nw) == 1) ? *(bv) : hash(bv, nw))
#define  HIT(h,bv,ss,nw) ((ss)->hash == (h) && ((nw) == 1 || \
		memcmp(VS(bv), VS((ss)->states), (nw)*sizeof(unsigned)) == 0))
	int			flags;
#define  STARTER	 01			/* 初始状态集 */
#define  POSTSTATE	 02			/* 包括目标状态 */
#define  LOCKED		 04			/* 锁定在缓存中 */
#define  NOPROGRESS  010		/* 零进展状态集 */
	struct arcp ins;			/* 指向此处的入弧链 */
	chr		   *lastseen;		/* 最后输入到达此处时 */
	struct sset **outs;			/* 按颜色索引的出弧向量 */
	struct arcp *inchain;		/* 出弧的链指针向量 */
};

struct dfa
{
	int			nssets;			/* 缓存的大小 */
	int			nssused;		/* 已占用的条目数量 */
	int			nstates;		/* 状态数量 */
	int			ncolors;		/* 出弧和入链向量的长度 */
	int			wordsper;		/* 状态集位向量的长度 */
	struct sset *ssets;			/* 状态集缓存 */
	unsigned   *statesarea;		/* 位向量存储 */
	unsigned   *work;			/* 指向状态区域内工作区的指针 */
	struct sset **outsarea;		/* 出弧向量存储 */
	struct arcp *incarea;		/* 入链存储 */
	struct cnfa *cnfa;
	struct colormap *cm;
	chr		   *lastpost;		/* 最后缓存刷新成功的位置 */
	chr		   *lastnopr;		/* 最后缓存刷新无进展的位置 */
	struct sset *search;		/* 替换搜索指针内存 */
	int			backno;			/* 如果DFA用于回溯引用，所引用的子编号 */
	short		backmin;		/* 回溯引用的最小重复次数 */
	short		backmax;		/* 回溯引用的最大重复次数 */
	bool		ismalloced;		/* 这个结构的dfa应该释放吗？ */
	bool		arraysmalloced; /* 是否应该释放其子数组? */
};

#define WORK	1				/* 需要的工作位向量的数量 */

/* 为小案例设置非malloc分配 */
#define FEWSTATES	20			/* 必须小于 UBITS */
#define FEWCOLORS	15
struct smalldfa
{
	struct dfa	dfa;			/* 必须在前 */
	struct sset ssets[FEWSTATES * 2];
	unsigned	statesarea[FEWSTATES * 2 + WORK];
	struct sset *outsarea[FEWSTATES * 2 * FEWCOLORS];
	struct arcp incarea[FEWSTATES * 2 * FEWCOLORS];
};

#define DOMALLOC	((struct smalldfa *)NULL)	/* 强制 malloc */



/* 内部变量，捆绑以便于传递 */
struct vars
{
	regex_t    *re;
	struct guts *g;
	int			eflags;			/* 参数的副本 */
	size_t		nmatch;
	regmatch_t *pmatch;
	rm_detail_t *details;
	chr		   *start;			/* 字符串开始 */
	chr		   *search_start;	/* 搜索字符串开始 */
	chr		   *stop;			/* 刚过字符串末尾 */
	int			err;			/* 如果有错误则返回错误代码 (0表示无) */
	struct dfa **subdfas;		/* 每棵树的子 DFAs */
	struct dfa **ladfas;		/* 每个拉康子 DFAs */
	struct sset **lblastcss;	/* 每个拉康子回溯重启数据 */
	chr		  **lblastcp;		/* 每个拉康子回溯重启数据 */
	struct smalldfa dfa1;
	struct smalldfa dfa2;
};

#define VISERR(vv)	((vv)->err != 0)	/* 我们是否已经看到错误？ */
#define ISERR() VISERR(v)
#define VERR(vv,e)	((vv)->err = ((vv)->err ? (vv)->err : (e)))
#define ERR(e)	VERR(v, e)		/* 记录一个错误 */
#define NOERR() {if (ISERR()) return v->err;}	/* 如果看到错误，返回它 */
#define OFF(p)	((p) - v->start)
#define LOFF(p) ((long)OFF(p))



/*
 * 前向声明
 */
/* === regexec.c === */
static struct dfa *getsubdfa(struct vars *, struct subre *);
static struct dfa *getladfa(struct vars *, int);
static int	find(struct vars *, struct cnfa *, struct colormap *);
static int	cfind(struct vars *, struct cnfa *, struct colormap *);
static int	cfindloop(struct vars *, struct cnfa *, struct colormap *, struct dfa *, struct dfa *, chr **);
static void zapallsubs(regmatch_t *, size_t);
static void zaptreesubs(struct vars *, struct subre *);
static void subset(struct vars *, struct subre *, chr *, chr *);
static int	cdissect(struct vars *, struct subre *, chr *, chr *);
static int	ccondissect(struct vars *, struct subre *, chr *, chr *);
static int	crevcondissect(struct vars *, struct subre *, chr *, chr *);
static int	cbrdissect(struct vars *, struct subre *, chr *, chr *);
static int	caltdissect(struct vars *, struct subre *, chr *, chr *);
static int	citerdissect(struct vars *, struct subre *, chr *, chr *);
static int	creviterdissect(struct vars *, struct subre *, chr *, chr *);

/* === rege_dfa.c === */
static chr *longest(struct vars *, struct dfa *, chr *, chr *, int *);
static chr *shortest(struct vars *, struct dfa *, chr *, chr *, chr *, chr **, int *);
static int	matchuntil(struct vars *, struct dfa *, chr *, struct sset **, chr **);
static chr *dfa_backref(struct vars *, struct dfa *, chr *, chr *, chr *, bool);
static chr *lastcold(struct vars *, struct dfa *);
static struct dfa *newdfa(struct vars *, struct cnfa *, struct colormap *, struct smalldfa *);
static void freedfa(struct dfa *);
static unsigned hash(unsigned *, int);
static struct sset *initialize(struct vars *, struct dfa *, chr *);
static struct sset *miss(struct vars *, struct dfa *, struct sset *, color, chr *, chr *);
static int	lacon(struct vars *, struct cnfa *, chr *, color);
static struct sset *getvacant(struct vars *, struct dfa *, chr *, chr *);
static struct sset *pickss(struct vars *, struct dfa *, chr *, chr *);


/*
 * pg_regexec - 匹配正则表达式
 */
int pg_regexec(regex_t *fc_re,
		   const chr *fc_string,
		   size_t fc_len,
		   size_t fc_search_start,
		   rm_detail_t *fc_details,
		   size_t fc_nmatch,
		   regmatch_t fc_pmatch[],
		   int fc_flags)
{
	struct vars fc_var;
	register struct vars *v = &fc_var;
	int			fc_st;
	size_t		fc_n;
	size_t		fc_i;
	int			fc_backref;

#define  LOCALMAT	 20
	regmatch_t	fc_mat[LOCALMAT];

#define  LOCALDFAS	 40
	struct dfa *fc_subdfas[LOCALDFAS];

	/* 运行检查 */
	if (fc_re == NULL || fc_string == NULL || fc_re->re_magic != REMAGIC)
		return REG_INVARG;
	if (fc_re->re_csize != sizeof(chr))
		return REG_MIXED;
	if (fc_search_start > fc_len)
		return REG_NOMATCH;

	/* 初始化区域相关支持 */
	pg_set_regex_collation(fc_re->re_collation);

	/* setup */
	v->re = fc_re;
	v->g = (struct guts *) fc_re->re_guts;
	if ((v->g->cflags & REG_EXPECT) && fc_details == NULL)
		return REG_INVARG;
	if (v->g->info & REG_UIMPOSSIBLE)
		return REG_NOMATCH;
	fc_backref = (v->g->info & REG_UBACKREF) ? 1 : 0;
	v->eflags = fc_flags;
	if (fc_backref && fc_nmatch <= v->g->nsub)
	{
		/* 需要更大的工作区域 */
		v->nmatch = v->g->nsub + 1;
		if (v->nmatch <= LOCALMAT)
			v->pmatch = fc_mat;
		else
			v->pmatch = (regmatch_t *) MALLOC(v->nmatch * sizeof(regmatch_t));
		if (v->pmatch == NULL)
			return REG_ESPACE;
		zapallsubs(v->pmatch, v->nmatch);
	}
	else
	{
		/* 我们可以直接在调用者的数组中存储结果 */
		v->pmatch = fc_pmatch;
		/* 确保调用者数组中的任何额外条目都填充为 -1 */
		if (fc_nmatch > 0)
			zapallsubs(fc_pmatch, fc_nmatch);
		/* 然后遗忘额外条目，以避免在 find() 中进行无用的工作 */
		if (fc_nmatch > v->g->nsub + 1)
			fc_nmatch = v->g->nsub + 1;
		v->nmatch = fc_nmatch;
	}
	v->details = fc_details;
	v->start = (chr *) fc_string;
	v->search_start = (chr *) fc_string + fc_search_start;
	v->stop = (chr *) fc_string + fc_len;
	v->err = 0;
	v->subdfas = NULL;
	v->ladfas = NULL;
	v->lblastcss = NULL;
	v->lblastcp = NULL;
	/* 在这一点以下，“goto cleanup”将正常工作 */

	assert(v->g->ntree >= 0);
	fc_n = (size_t) v->g->ntree;
	if (fc_n <= LOCALDFAS)
		v->subdfas = fc_subdfas;
	else
	{
		v->subdfas = (struct dfa **) MALLOC(fc_n * sizeof(struct dfa *));
		if (v->subdfas == NULL)
		{
			fc_st = REG_ESPACE;
			goto cleanup;
		}
	}
	for (fc_i = 0; fc_i < fc_n; fc_i++)
		v->subdfas[fc_i] = NULL;

	assert(v->g->nlacons >= 0);
	fc_n = (size_t) v->g->nlacons;
	if (fc_n > 0)
	{
		v->ladfas = (struct dfa **) MALLOC(fc_n * sizeof(struct dfa *));
		if (v->ladfas == NULL)
		{
			fc_st = REG_ESPACE;
			goto cleanup;
		}
		for (fc_i = 0; fc_i < fc_n; fc_i++)
			v->ladfas[fc_i] = NULL;
		v->lblastcss = (struct sset **) MALLOC(fc_n * sizeof(struct sset *));
		v->lblastcp = (chr **) MALLOC(fc_n * sizeof(chr *));
		if (v->lblastcss == NULL || v->lblastcp == NULL)
		{
			fc_st = REG_ESPACE;
			goto cleanup;
		}
		for (fc_i = 0; fc_i < fc_n; fc_i++)
		{
			v->lblastcss[fc_i] = NULL;
			v->lblastcp[fc_i] = NULL;
		}
	}

	/* do it */
	assert(v->g->tree != NULL);
	if (fc_backref)
		fc_st = cfind(v, &v->g->tree->cnfa, &v->g->cmap);
	else
		fc_st = find(v, &v->g->tree->cnfa, &v->g->cmap);

	/* 在成功时，确保调用者的匹配向量正确填充 */
	if (fc_st == REG_OKAY && fc_nmatch > 0)
	{
		if (v->pmatch != fc_pmatch)
		{
			/* 从（更大的）工作区域复制匹配向量的部分 */
			assert(fc_nmatch <= v->nmatch);
			memcpy(VS(fc_pmatch), VS(v->pmatch), fc_nmatch * sizeof(regmatch_t));
		}
		if (v->g->cflags & REG_NOSUB)
		{
			/* 不向调用者暴露可能部分匹配的结果 */
			zapallsubs(fc_pmatch, fc_nmatch);
		}
	}

	/* 清理 */
cleanup:
	if (v->pmatch != fc_pmatch && v->pmatch != fc_mat)
		FREE(v->pmatch);
	if (v->subdfas != NULL)
	{
		fc_n = (size_t) v->g->ntree;
		for (fc_i = 0; fc_i < fc_n; fc_i++)
		{
			if (v->subdfas[fc_i] != NULL)
				freedfa(v->subdfas[fc_i]);
		}
		if (v->subdfas != fc_subdfas)
			FREE(v->subdfas);
	}
	if (v->ladfas != NULL)
	{
		fc_n = (size_t) v->g->nlacons;
		for (fc_i = 0; fc_i < fc_n; fc_i++)
		{
			if (v->ladfas[fc_i] != NULL)
				freedfa(v->ladfas[fc_i]);
		}
		FREE(v->ladfas);
	}
	if (v->lblastcss != NULL)
		FREE(v->lblastcss);
	if (v->lblastcp != NULL)
		FREE(v->lblastcp);

#ifdef REG_DEBUG
	if (v->eflags & (REG_FTRACE | REG_MTRACE))
		fflush(stdout);
#endif

	return fc_st;
}

/*
 * getsubdfa - 为一个树子正则节点创建或重新获取 DFA
 *
 * 我们只需要在每次总体正则表达式执行中创建一次 DFA。
 * DFA 将在 pg_regexec() 的清理步骤中被释放。
 */
static struct dfa * getsubdfa(struct vars *v,
		  struct subre *fc_t)
{
	struct dfa *fc_d = v->subdfas[fc_t->id];

	if (fc_d == NULL)
	{
		fc_d = newdfa(v, &fc_t->cnfa, &v->g->cmap, DOMALLOC);
		if (fc_d == NULL)
			return NULL;
		/* 如果这是一个反向引用节点，设置附加信息 */
		if (fc_t->op == 'b')
		{
			fc_d->backno = fc_t->backno;
			fc_d->backmin = fc_t->min;
			fc_d->backmax = fc_t->max;
		}
		v->subdfas[fc_t->id] = fc_d;
	}
	return fc_d;
}

/*
 * getladfa - 为 LACON 子正则节点创建或重新获取 DFA
 *
 * 与上面相同，但针对 LACONs。
 */
static struct dfa * getladfa(struct vars *v,
		 int n)
{
	assert(n > 0 && n < v->g->nlacons && v->g->lacons != NULL);

	if (v->ladfas[n] == NULL)
	{
		struct subre *sub = &v->g->lacons[n];

		v->ladfas[n] = newdfa(v, &sub->cnfa, &v->g->cmap, DOMALLOC);
		/* 一个 LACON 不能包含回溯，因此没有其他事情要做 */
	}
	return v->ladfas[n];
}

/*
 * find - 找到主 NFA 的匹配（无复杂情况）
 */
static int find(struct vars *v,
	 struct cnfa *fc_cnfa,
	 struct colormap *fc_cm)
{
	struct dfa *fc_s;
	struct dfa *fc_d;
	chr		   *fc_begin;
	chr		   *fc_end = NULL;
	chr		   *fc_cold;
	chr		   *fc_open;			/* 可行起始范围的开口和闭口 */
	chr		   *fc_close;
	int			fc_hitend;
	int			fc_shorter = (v->g->tree->flags & SHORTER) ? 1 : 0;

	/* 首先，使用搜索 RE 尝试一下 */
	fc_s = newdfa(v, &v->g->search, fc_cm, &v->dfa1);
	if (fc_s == NULL)
		return v->err;
	MDEBUG(("\nsearch at %ld\n", LOFF(v->start)));
	fc_cold = NULL;
	fc_close = shortest(v, fc_s, v->search_start, v->search_start, v->stop,
					 &fc_cold, (int *) NULL);
	freedfa(fc_s);
	NOERR();
	if (v->g->cflags & REG_EXPECT)
	{
		assert(v->details != NULL);
		if (fc_cold != NULL)
			v->details->rm_extend.rm_so = OFF(fc_cold);
		else
			v->details->rm_extend.rm_so = OFF(v->stop);
		v->details->rm_extend.rm_eo = OFF(v->stop); /* 未知 */
	}
	if (fc_close == NULL)			/* 未找到 */
		return REG_NOMATCH;
	if (v->nmatch == 0)			/* 找到了，不需要确切位置 */
		return REG_OKAY;

	/* 找到起始点并匹配 */
	assert(fc_cold != NULL);
	fc_open = fc_cold;
	fc_cold = NULL;
	MDEBUG(("between %ld and %ld\n", LOFF(fc_open), LOFF(fc_close)));
	fc_d = newdfa(v, fc_cnfa, fc_cm, &v->dfa1);
	if (fc_d == NULL)
		return v->err;
	for (fc_begin = fc_open; fc_begin <= fc_close; fc_begin++)
	{
		MDEBUG(("\nfind trying at %ld\n", LOFF(fc_begin)));
		if (fc_shorter)
			fc_end = shortest(v, fc_d, fc_begin, fc_begin, v->stop,
						   (chr **) NULL, &fc_hitend);
		else
			fc_end = longest(v, fc_d, fc_begin, v->stop, &fc_hitend);
		if (ISERR())
		{
			freedfa(fc_d);
			return v->err;
		}
		if (fc_hitend && fc_cold == NULL)
			fc_cold = fc_begin;
		if (fc_end != NULL)
			break;				/* 注意突破 */
	}
	assert(fc_end != NULL);		/* 搜索 RE 成功，因此循环应该 */
	freedfa(fc_d);

	/* 并固定细节 */
	assert(v->nmatch > 0);
	v->pmatch[0].rm_so = OFF(fc_begin);
	v->pmatch[0].rm_eo = OFF(fc_end);
	if (v->g->cflags & REG_EXPECT)
	{
		if (fc_cold != NULL)
			v->details->rm_extend.rm_so = OFF(fc_cold);
		else
			v->details->rm_extend.rm_so = OFF(v->stop);
		v->details->rm_extend.rm_eo = OFF(v->stop); /* 未知 */
	}
	if (v->nmatch == 1)			/* 不需要子匹配 */
		return REG_OKAY;

	/* 找到子匹配 */
	return cdissect(v, v->g->tree, fc_begin, fc_end);
}

/*
 * cfind - 找到主 NFA 的匹配（有复杂情况）
 */
static int cfind(struct vars *v,
	  struct cnfa *fc_cnfa,
	  struct colormap *fc_cm)
{
	struct dfa *fc_s;
	struct dfa *fc_d;
	chr		   *fc_cold;
	int			fc_ret;

	fc_s = newdfa(v, &v->g->search, fc_cm, &v->dfa1);
	if (fc_s == NULL)
		return v->err;
	fc_d = newdfa(v, fc_cnfa, fc_cm, &v->dfa2);
	if (fc_d == NULL)
	{
		freedfa(fc_s);
		return v->err;
	}

	fc_ret = cfindloop(v, fc_cnfa, fc_cm, fc_d, fc_s, &fc_cold);

	freedfa(fc_d);
	freedfa(fc_s);
	NOERR();
	if (v->g->cflags & REG_EXPECT)
	{
		assert(v->details != NULL);
		if (fc_cold != NULL)
			v->details->rm_extend.rm_so = OFF(fc_cold);
		else
			v->details->rm_extend.rm_so = OFF(v->stop);
		v->details->rm_extend.rm_eo = OFF(v->stop); /* 未知 */
	}
	return fc_ret;
}

/*
 * cfindloop - cfind 的核心
 */
static int cfindloop(struct vars *v,
		  struct cnfa *fc_cnfa,
		  struct colormap *fc_cm,
		  struct dfa *fc_d,
		  struct dfa *fc_s,
		  chr **fc_coldp)			/* 将 coldstart 指针放在哪里 */
{
	chr		   *fc_begin;
	chr		   *fc_end;
	chr		   *fc_cold;
	chr		   *fc_open;			/* 可行起始范围的开口和闭口 */
	chr		   *fc_close;
	chr		   *fc_estart;
	chr		   *fc_estop;
	int			fc_er;
	int			fc_shorter = v->g->tree->flags & SHORTER;
	int			fc_hitend;

	assert(fc_d != NULL && fc_s != NULL);
	fc_cold = NULL;
	fc_close = v->search_start;
	do
	{
		/* 使用搜索 RE 在 "close" 处/之后搜索匹配范围 */
		MDEBUG(("\ncsearch at %ld\n", LOFF(fc_close)));
		fc_close = shortest(v, fc_s, fc_close, fc_close, v->stop, &fc_cold, (int *) NULL);
		if (ISERR())
		{
			*fc_coldp = fc_cold;
			return v->err;
		}
		if (fc_close == NULL)
			break;				/* 在任何地方都没有更多可能的匹配 */
		assert(fc_cold != NULL);
		fc_open = fc_cold;
		fc_cold = NULL;
		/* 查找在 "open" 和 "close" 之间（包括）的匹配 */
		MDEBUG(("cbetween %ld and %ld\n", LOFF(fc_open), LOFF(fc_close)));
		for (fc_begin = fc_open; fc_begin <= fc_close; fc_begin++)
		{
			MDEBUG(("\ncfind trying at %ld\n", LOFF(fc_begin)));
			fc_estart = fc_begin;
			fc_estop = v->stop;
			for (;;)
			{
				/* 在这里我们使用顶节点的详细 RE */
				if (fc_shorter)
					fc_end = shortest(v, fc_d, fc_begin, fc_estart,
								   fc_estop, (chr **) NULL, &fc_hitend);
				else
					fc_end = longest(v, fc_d, fc_begin, fc_estop,
								  &fc_hitend);
				if (ISERR())
				{
					*fc_coldp = fc_cold;
					return v->err;
				}
				if (fc_hitend && fc_cold == NULL)
					fc_cold = fc_begin;
				if (fc_end == NULL)
					break;		/* 使用这个起始点没有匹配，尝试下一个 */
				MDEBUG(("tentative end %ld\n", LOFF(fc_end)));
				/* 解剖潜在匹配以查看是否真的匹配 */
				fc_er = cdissect(v, v->g->tree, fc_begin, fc_end);
				if (fc_er == REG_OKAY)
				{
					if (v->nmatch > 0)
					{
						v->pmatch[0].rm_so = OFF(fc_begin);
						v->pmatch[0].rm_eo = OFF(fc_end);
					}
					*fc_coldp = fc_cold;
					return REG_OKAY;
				}
				if (fc_er != REG_NOMATCH)
				{
					ERR(fc_er);
					*fc_coldp = fc_cold;
					return fc_er;
				}
				/* 尝试下一个更长/更短的匹配，起始点相同 */
				if (fc_shorter)
				{
					if (fc_end == fc_estop)
						break;	/* 没有更多匹配，因此尝试下一个起始点 */
					fc_estart = fc_end + 1;
				}
				else
				{
					if (fc_end == fc_begin)
						break;	/* 没有更多匹配，因此尝试下一个起始点 */
					fc_estop = fc_end - 1;
				}
			}					/* 结束终点位置的循环 */
		}						/* 结束起始位置的循环 */

		/*
		 * 如果我们到了这里，在 "close" 处或之前没有可能的匹配，
		 * 因此考虑超出该范围的匹配。我们将使用搜索 RE 进行全新的搜索
		 * 以找到新的有希望的匹配范围。
		 */
		fc_close++;
	} while (fc_close < v->stop);

	*fc_coldp = fc_cold;
	return REG_NOMATCH;
}

/*
 * zapallsubs - 将所有子表达式匹配初始化为 "没有匹配"
 *
 * 请注意，p[0]，整体匹配位置，不会被触及。
 */
static void zapallsubs(regmatch_t *fc_p,
		   size_t fc_n)
{
	size_t		fc_i;

	for (fc_i = fc_n - 1; fc_i > 0; fc_i--)
	{
		fc_p[fc_i].rm_so = -1;
		fc_p[fc_i].rm_eo = -1;
	}
}

/*
 * zaptreesubs - 将子树中的子表达式初始化为 "没有匹配"
 */
static void zaptreesubs(struct vars *v,
			struct subre *fc_t)
{
	int			fc_n = fc_t->capno;
	struct subre *fc_t2;

	if (fc_n > 0)
	{
		if ((size_t) fc_n < v->nmatch)
		{
			v->pmatch[fc_n].rm_so = -1;
			v->pmatch[fc_n].rm_eo = -1;
		}
	}

	for (fc_t2 = fc_t->child; fc_t2 != NULL; fc_t2 = fc_t2->sibling)
		zaptreesubs(v, fc_t2);
}

/*
 * subset - 为成功的子 RE 设置子表达式匹配数据
 */
static void subset(struct vars *v,
	   struct subre *fc_sub,
	   chr *fc_begin,
	   chr *fc_end)
{
	int			fc_n = fc_sub->capno;

	assert(fc_n > 0);
	if ((size_t) fc_n >= v->nmatch)
		return;

	MDEBUG(("%d: setting %d = %ld-%ld\n", fc_sub->id, fc_n, LOFF(fc_begin), LOFF(fc_end)));
	v->pmatch[fc_n].rm_so = OFF(fc_begin);
	v->pmatch[fc_n].rm_eo = OFF(fc_end);
}

/*
 * cdissect - 检查回溯并确定子表达式匹配
 *
 * cdissect 递归处理子 RE 树，以检查回溯的匹配
 * 和/或识别捕获节点的子匹配边界。拟议的匹配
 * 从 "begin" 到 "end"（不包括 "end"），基本上
 * 我们在 "解剖" 它以查看子匹配的位置。
 *
 * 在调用任何级别的 cdissect 之前，调用者必须运行节点的
 * DFA 并发现拟议的子字符串满足 DFA。（我们让
 * 调用者这样做，因为在连接和迭代节点中，
 * 检查所有子字符串与子 DFA 的匹配要快得多，
 * 然后我们再递归。）
 *
 * 成功匹配的副作用是保存匹配位置以
 * 捕获子表达式到 v->pmatch[] 中。这有点棘手，
 * 所以我们制定以下规则：
 * 1. 在初始进入 cdissect 之前，所有匹配数据必须
 *    被清除（这是通过 zapallsubs 完成的）。
 * 2. 在任何递归进入 cdissect 之前，必须保证
 *    清除该子表达式树的匹配数据（见 zaptreesubs）。
 * 3. 返回 REG_OKAY 时，cdissect 的每一级将保存
 *    任何相关的匹配位置。
 * 4. 返回 REG_NOMATCH 时，cdissect 的每一级将保证
 *    它的子表达式匹配位置再次清除。
 * 5. 对于错误情况（即其他结果代码）不做任何保证。
 * 6. 当 cdissect 的某个级别放弃成功的子匹配时，它将
 *    在尝试该子树或其右侧的任何子树的任何新 DFA 匹配或
 *    cdissect 调用之前，用 zaptreesubs 清除该子树的匹配位置
 *    （也就是说，任何可能对已放弃匹配有回溯的子树）。
 * 这可能看起来过于复杂，但由于必须在
 * 任何新的 DFA 匹配之前重置匹配位置的规定，
 * 因此很难简化这一点（这是确保 dfa_backref 安全所需要的规则）。
 * 这意味着不能只在每个 cdissect 级别的开始时重置相关的匹配位置。
 */
static int						/* regexec 返回代码 */
cdissect(struct vars *v,
		 struct subre *fc_t,
		 chr *fc_begin,			/* 相关子字符串的开始 */
		 chr *fc_end)				/* 结束部分 */
{
	int			fc_er;

	assert(fc_t != NULL);
	MDEBUG(("%d: cdissect %c %ld-%ld\n", fc_t->id, fc_t->op, LOFF(fc_begin), LOFF(fc_end)));

	/* 检查操作取消的便利位置 */
	if (CANCEL_REQUESTED(v->re))
		return REG_CANCEL;
	/* ... 和栈溢出 */
	if (STACK_TOO_DEEP(v->re))
		return REG_ETOOBIG;

	switch (fc_t->op)
	{
		case '=':				/* 终端节点 */
			assert(fc_t->child == NULL);
			fc_er = REG_OKAY;		/* 不执行任何操作，父节点已经完成工作 */
			break;
		case 'b':				/* 反向引用 */
			assert(fc_t->child == NULL);
			fc_er = cbrdissect(v, fc_t, fc_begin, fc_end);
			break;
		case '.':				/* 连接 */
			assert(fc_t->child != NULL);
			if (fc_t->child->flags & SHORTER)	/* 反向扫描 */
				fc_er = crevcondissect(v, fc_t, fc_begin, fc_end);
			else
				fc_er = ccondissect(v, fc_t, fc_begin, fc_end);
			break;
		case '|':				/* 交替 */
			assert(fc_t->child != NULL);
			fc_er = caltdissect(v, fc_t, fc_begin, fc_end);
			break;
		case '*':				/* 迭代 */
			assert(fc_t->child != NULL);
			if (fc_t->child->flags & SHORTER)	/* 反向扫描 */
				fc_er = creviterdissect(v, fc_t, fc_begin, fc_end);
			else
				fc_er = citerdissect(v, fc_t, fc_begin, fc_end);
			break;
		case '(':				/* 不执行操作的捕获节点 */
			assert(fc_t->child != NULL);
			fc_er = cdissect(v, fc_t->child, fc_begin, fc_end);
			break;
		default:
			fc_er = REG_ASSERT;
			break;
	}

	/*
	 * 除非回溯引用在下面潜伏，否则我们绝不应该有匹配失败；
	 * 否则，要么调用者未能检查 DFA，要么 DFA 与节点内部存在某种不一致。
	 */
	assert(fc_er != REG_NOMATCH || (fc_t->flags & BACKR));

	/*
	 * 如果该节点被标记为捕获，则保存成功匹配的位置。
	 */
	if (fc_t->capno > 0 && fc_er == REG_OKAY)
		subset(v, fc_t, fc_begin, fc_end);

	return fc_er;
}

/*
 * ccondissect - 解剖连接节点的匹配
 */
static int						/* regexec 返回代码 */
ccondissect(struct vars *v,
			struct subre *fc_t,
			chr *fc_begin,			/* 相关子字符串的开始 */
			chr *fc_end)			/* 结束部分 */
{
#ifdef FDD //cppcheck
	struct subre *fc_left = NULL;
	struct subre * fc_right= NULL;
	struct dfa *fc_d;
	struct dfa *fc_d2;
	chr		   *fc_mid;
	int			fc_er;

	assert(fc_t && fc_t->child);
	
	fc_left =  fc_t->child;
	
	assert(fc_left != NULL && fc_left->cnfa.nstates > 0);
	
	fc_right =  fc_left->sibling;
	
#else
	struct subre *fc_left = fc_t->child;
	struct subre *fc_right = fc_left->sibling;
	struct dfa *fc_d;
	struct dfa *fc_d2;
	chr		   *fc_mid;
	int			fc_er;

	assert(fc_t->op == '.');
	assert(fc_left != NULL && fc_left->cnfa.nstates > 0);
#endif
	assert(fc_right != NULL && fc_right->cnfa.nstates > 0);
	assert(fc_right->sibling == NULL);
	assert(!(fc_left->flags & SHORTER));

	fc_d = getsubdfa(v, fc_left);
	NOERR();
	fc_d2 = getsubdfa(v, fc_right);
	NOERR();
	MDEBUG(("%d: ccondissect %ld-%ld\n", fc_t->id, LOFF(fc_begin), LOFF(fc_end)));

	/* 选择一个临时中点 */
	fc_mid = longest(v, fc_d, fc_begin, fc_end, (int *) NULL);
	NOERR();
	if (fc_mid == NULL)
		return REG_NOMATCH;
	MDEBUG(("%d: tentative midpoint %ld\n", fc_t->id, LOFF(fc_mid)));

	/* 迭代直到满意或失败 */
	for (;;)
	{
		/* 试试这个中点的大小 */
		if (longest(v, fc_d2, fc_mid, fc_end, (int *) NULL) == fc_end)
		{
			fc_er = cdissect(v, fc_left, fc_begin, fc_mid);
			if (fc_er == REG_OKAY)
			{
				fc_er = cdissect(v, fc_right, fc_mid, fc_end);
				if (fc_er == REG_OKAY)
				{
					/* 满意 */
					MDEBUG(("%d: successful\n", fc_t->id));
					return REG_OKAY;
				}
				/* 重置左侧的匹配（右侧应该已经自己完成这一步） */
				zaptreesubs(v, fc_left);
			}
			if (fc_er != REG_NOMATCH)
				return fc_er;
		}
		NOERR();

		/* 该中点不工作，找到一个新的 */
		if (fc_mid == fc_begin)
		{
			/* 所有可能性已耗尽 */
			MDEBUG(("%d: no midpoint\n", fc_t->id));
			return REG_NOMATCH;
		}
		fc_mid = longest(v, fc_d, fc_begin, fc_mid - 1, (int *) NULL);
		NOERR();
		if (fc_mid == NULL)
		{
			/* 未能找到新的 */
			MDEBUG(("%d: failed midpoint\n", fc_t->id));
			return REG_NOMATCH;
		}
		MDEBUG(("%d: new midpoint %ld\n", fc_t->id, LOFF(fc_mid)));
	}

	/* 不能到这里 */
	return REG_ASSERT;
}

/*
 * crevcondissect - 解剖连接节点的匹配，优先短的
 */
static int						/* regexec 返回代码 */
crevcondissect(struct vars *v,
			   struct subre *fc_t,
			   chr *fc_begin,		/* 相关子字符串的开始 */
			   chr *fc_end)		/* 结束部分 */
{
#ifdef FDD //cppcheck
	struct subre *fc_left = NULL;
	struct subre *fc_right = NULL;
#else
	struct subre *fc_left = fc_t->child;
	struct subre *fc_right = fc_left->sibling;
#endif
	struct dfa *fc_d;
	struct dfa *fc_d2;
	chr		   *fc_mid;
	int			fc_er;

#ifdef FDD //cppcheck
	assert(fc_t && fc_t->child);
	fc_left = fc_t->child;
	assert(fc_left != NULL && fc_left->cnfa.nstates > 0);
	fc_right = fc_left->sibling;
#endif
	assert(fc_t->op == '.');
#ifndef FDD //cppcheck	
	assert(fc_left != NULL && fc_left->cnfa.nstates > 0);
#endif
	assert(fc_right != NULL && fc_right->cnfa.nstates > 0);
	assert(fc_right->sibling == NULL);
	assert(fc_left->flags & SHORTER);

	fc_d = getsubdfa(v, fc_left);
	NOERR();
	fc_d2 = getsubdfa(v, fc_right);
	NOERR();
	MDEBUG(("%d: crevcondissect %ld-%ld\n", fc_t->id, LOFF(fc_begin), LOFF(fc_end)));

	/* 选择一个临时中点 */
	fc_mid = shortest(v, fc_d, fc_begin, fc_begin, fc_end, (chr **) NULL, (int *) NULL);
	NOERR();
	if (fc_mid == NULL)
		return REG_NOMATCH;
	MDEBUG(("%d: tentative midpoint %ld\n", fc_t->id, LOFF(fc_mid)));

	/* 迭代直到满意或失败 */
	for (;;)
	{
		/* 试试这个中点的大小 */
		if (longest(v, fc_d2, fc_mid, fc_end, (int *) NULL) == fc_end)
		{
			fc_er = cdissect(v, fc_left, fc_begin, fc_mid);
			if (fc_er == REG_OKAY)
			{
				fc_er = cdissect(v, fc_right, fc_mid, fc_end);
				if (fc_er == REG_OKAY)
				{
					/* 满意 */
					MDEBUG(("%d: successful\n", fc_t->id));
					return REG_OKAY;
				}
				/* 重置左侧的匹配（右侧应该已经自己完成这一步） */
				zaptreesubs(v, fc_left);
			}
			if (fc_er != REG_NOMATCH)
				return fc_er;
		}
		NOERR();

		/* 该中点不工作，找到一个新的 */
		if (fc_mid == fc_end)
		{
			/* 所有可能性已耗尽 */
			MDEBUG(("%d: no midpoint\n", fc_t->id));
			return REG_NOMATCH;
		}
		fc_mid = shortest(v, fc_d, fc_begin, fc_mid + 1, fc_end, (chr **) NULL, (int *) NULL);
		NOERR();
		if (fc_mid == NULL)
		{
			/* 未能找到新的 */
			MDEBUG(("%d: failed midpoint\n", fc_t->id));
			return REG_NOMATCH;
		}
		MDEBUG(("%d: new midpoint %ld\n", fc_t->id, LOFF(fc_mid)));
	}

	/* 不能到这里 */
	return REG_ASSERT;
}

/*
 * cbrdissect - 解剖回溯引用节点的匹配
 *
 * 回溯引用的匹配可能已经通过 dfa_backref() 验证，
 * 但我们不能确定，因此必须在这里检查它。
 */
static int						/* regexec 返回代码 */
cbrdissect(struct vars *v,
		   struct subre *fc_t,
		   chr *fc_begin,			/* 相关子字符串的开始 */
		   chr *fc_end)			/* 结束部分 */
{
	int			fc_n = fc_t->backno;
	size_t		fc_numreps;
	size_t		fc_tlen;
	size_t		fc_brlen;
	chr		   *fc_brstring;
	chr		   *fc_p;
	int			fc_min = fc_t->min;
	int			fc_max = fc_t->max;

	assert(fc_t != NULL);
	assert(fc_t->op == 'b');
	assert(fc_n >= 0);
	assert((size_t) fc_n < v->nmatch);

	MDEBUG(("%d: cbrdissect %d{%d-%d} %ld-%ld\n", fc_t->id, fc_n, fc_min, fc_max,
			LOFF(fc_begin), LOFF(fc_end)));

	/* 获取回溯引用的字符串 */
	if (v->pmatch[fc_n].rm_so == -1)
		return REG_NOMATCH;
	fc_brstring = v->start + v->pmatch[fc_n].rm_so;
	fc_brlen = v->pmatch[fc_n].rm_eo - v->pmatch[fc_n].rm_so;

	/* 零长度字符串的特殊情况 */
	if (fc_brlen == 0)
	{
		/*
		 * 仅当目标长度为零时匹配，但可以考虑存在任意数量的
		 * 重复
		 */
		if (fc_begin == fc_end && fc_min <= fc_max)
		{
			MDEBUG(("%d: backref matched trivially\n", fc_t->id));
			return REG_OKAY;
		}
		return REG_NOMATCH;
	}
	if (fc_begin == fc_end)
	{
		/* 仅当零次重复是可接受的情况下匹配 */
		if (fc_min == 0)
		{
			MDEBUG(("%d: backref matched trivially\n", fc_t->id));
			return REG_OKAY;
		}
		return REG_NOMATCH;
	}

	/*
	 * 检查目标长度以查看它是否可能是 brstring 的允许重复次数
	 */
	assert(fc_end > fc_begin);
	fc_tlen = fc_end - fc_begin;
	if (fc_tlen % fc_brlen != 0)
		return REG_NOMATCH;
	fc_numreps = fc_tlen / fc_brlen;
	if (fc_numreps < fc_min || (fc_numreps > fc_max && fc_max != DUPINF))
		return REG_NOMATCH;

	/* 好吧，比较实际的字符串内容 */
	fc_p = fc_begin;
	while (fc_numreps-- > 0)
	{
		if ((*v->g->compare) (fc_brstring, fc_p, fc_brlen) != 0)
			return REG_NOMATCH;
		fc_p += fc_brlen;
	}

	MDEBUG(("%d: backref matched\n", fc_t->id));
	return REG_OKAY;
}

/*
 * caltdissect - 切分交替节点匹配
 */
static int						/* regexec 返回代码 */
caltdissect(struct vars *v,
			struct subre *fc_t,
			chr *fc_begin,			/* 相关子字符串的开始 */
			chr *fc_end)			/* 结束部分 */
{
	struct dfa *fc_d;
	int			fc_er;

	assert(fc_t->op == '|');

	fc_t = fc_t->child;
	/* 至少应该有 2 个替代方案 */
	assert(fc_t != NULL && fc_t->sibling != NULL);

	while (fc_t != NULL)
	{
		assert(fc_t->cnfa.nstates > 0);

		MDEBUG(("%d: caltdissect %ld-%ld\n", fc_t->id, LOFF(fc_begin), LOFF(fc_end)));

		fc_d = getsubdfa(v, fc_t);
		NOERR();
		if (longest(v, fc_d, fc_begin, fc_end, (int *) NULL) == fc_end)
		{
			MDEBUG(("%d: caltdissect matched\n", fc_t->id));
			fc_er = cdissect(v, fc_t, fc_begin, fc_end);
			if (fc_er != REG_NOMATCH)
				return fc_er;
		}
		NOERR();

		fc_t = fc_t->sibling;
	}

	return REG_NOMATCH;
}

/*
 * citerdissect - 解析迭代节点的匹配
 */
static int						/* regexec 返回代码 */
citerdissect(struct vars *v,
			 struct subre *fc_t,
			 chr *fc_begin,		/* 相关子字符串的开始 */
			 chr *fc_end)			/* 结束部分 */
{
	struct dfa *fc_d;
	chr		  **fc_endpts;
	chr		   *fc_limit;
	int			fc_min_matches;
	size_t		fc_max_matches;
	int			fc_nverified;
	int			fc_k;
	int			fc_i;
	int			fc_er;

	assert(fc_t->op == '*');
	assert(fc_t->child != NULL && fc_t->child->cnfa.nstates > 0);
	assert(!(fc_t->child->flags & SHORTER));
	assert(fc_begin <= fc_end);

	MDEBUG(("%d: citerdissect %ld-%ld\n", fc_t->id, LOFF(fc_begin), LOFF(fc_end)));

	/*
	 * 目前假设最小匹配数量为 1。如果允许零个匹配，并且目标字符串为空，
	 * 我们可以匹配，无论迭代节点的内容如何 —— 但我们更希望至少匹配一次，以便捕捉括号被设置。
	 * （这里的一个担忧的例子是一个模式像 "()*\1"，历史上这个
	 * 代码允许它成功。）因此，我们在底部处理零匹配的情况，
	 * 在未找到任何其他匹配方式后。
	 */
	fc_min_matches = fc_t->min;
	if (fc_min_matches <= 0)
		fc_min_matches = 1;

	/*
	 * 我们需要工作区来跟踪每个子匹配的端点。通常情况下，
	 * 我们只考虑非零长度的子匹配，因此最多可以有 end-begin 个。
	 * 不过，如果 min 大于该值，我们还将考虑零长度的子匹配以找到足够的匹配。
	 *
	 * 为了方便，endpts[0] 包含“开始”指针，我们将
	 * 子匹配端点存储在 endpts[1..max_matches] 中。
	 */
	fc_max_matches = fc_end - fc_begin;
	if (fc_max_matches > fc_t->max && fc_t->max != DUPINF)
		fc_max_matches = fc_t->max;
	if (fc_max_matches < fc_min_matches)
		fc_max_matches = fc_min_matches;
	fc_endpts = (chr **) MALLOC((fc_max_matches + 1) * sizeof(chr *));
	if (fc_endpts == NULL)
		return REG_ESPACE;
	fc_endpts[0] = fc_begin;

	fc_d = getsubdfa(v, fc_t->child);
	if (ISERR())
	{
		FREE(fc_endpts);
		return v->err;
	}

	/*
	 * 我们的策略是首先找到一组根据子节点的 DFA
	 * 有效的子匹配端点，然后递归解析每个子匹配以确认有效性。
	 * 如果任何有效性检查失败，回溯该子匹配并重试。
	 * 当我们下次进行有效性检查时，我们不必重新检查
	 * 任何我们没有移动端点的成功验证的子匹配。nverified 记住
	 * 当前已知的有效子匹配数量。
	 */

	/* 初始化考虑第一个子匹配 */
	fc_nverified = 0;
	fc_k = 1;
	fc_limit = fc_end;

	/* 迭代直到满意或失败 */
	while (fc_k > 0)
	{
		/* 尝试为第 k 个子匹配找到端点 */
		fc_endpts[fc_k] = longest(v, fc_d, fc_endpts[fc_k - 1], fc_limit, (int *) NULL);
		if (ISERR())
		{
			FREE(fc_endpts);
			return v->err;
		}
		if (fc_endpts[fc_k] == NULL)
		{
			/* 无法匹配，因此查看我们是否可以缩短上一个匹配 */
			fc_k--;
			goto backtrack;
		}
		MDEBUG(("%d: working endpoint %d: %ld\n",
				fc_t->id, fc_k, LOFF(fc_endpts[fc_k])));

		/* 第 k 个子匹配不再被视为已验证 */
		if (fc_nverified >= fc_k)
			fc_nverified = fc_k - 1;

		if (fc_endpts[fc_k] != fc_end)
		{
			/* 还没有到达结尾，如果允许，则尝试另一个迭代 */
			if (fc_k >= fc_max_matches)
			{
				/* 必须尝试缩短某个先前的匹配 */
				fc_k--;
				goto backtrack;
			}

			/* 除非必要，否则拒绝零长度匹配 */
			if (fc_endpts[fc_k] == fc_endpts[fc_k - 1] &&
				(fc_k >= fc_min_matches || fc_min_matches - fc_k < fc_end - fc_endpts[fc_k]))
				goto backtrack;

			fc_k++;
			fc_limit = fc_end;
			continue;
		}

		/*
		 * 我们已确定一种将字符串划分为 k 个子匹配的方式，
		 * 根据子 DFA 截至目前为止是有效的。如果 k 是允许的匹配数量，
		 * 开始回归的慢部分：递归以验证每个子匹配。
		 * 我们始终有 k <= max_matches，无需检查。
		 */
		if (fc_k < fc_min_matches)
			goto backtrack;

		MDEBUG(("%d: verifying %d..%d\n", fc_t->id, fc_nverified + 1, fc_k));

		for (fc_i = fc_nverified + 1; fc_i <= fc_k; fc_i++)
		{
			/* 从非最后一个迭代中删除任何匹配数据 */
			zaptreesubs(v, fc_t->child);
			fc_er = cdissect(v, fc_t->child, fc_endpts[fc_i - 1], fc_endpts[fc_i]);
			if (fc_er == REG_OKAY)
			{
				fc_nverified = fc_i;
				continue;
			}
			if (fc_er == REG_NOMATCH)
				break;
			/* 哎呀，出现问题了 */
			FREE(fc_endpts);
			return fc_er;
		}

		if (fc_i > fc_k)
		{
			/* 满意 */
			MDEBUG(("%d: successful\n", fc_t->id));
			FREE(fc_endpts);
			return REG_OKAY;
		}

		/* 第 i 个匹配未能验证，因此回溯它 */
		fc_k = fc_i;

backtrack:

		/*
		 * 必须考虑第 k 个子匹配的更短版本。
		 * 不过，只有在必要时才会要求零长度匹配。
		 */
		while (fc_k > 0)
		{
			chr		   *fc_prev_end = fc_endpts[fc_k - 1];

			if (fc_endpts[fc_k] > fc_prev_end)
			{
				fc_limit = fc_endpts[fc_k] - 1;
				if (fc_limit > fc_prev_end ||
					(fc_k < fc_min_matches && fc_min_matches - fc_k >= fc_end - fc_prev_end))
				{
					/* 跳出回溯循环，继续外部循环 */
					break;
				}
			}
			/* 无法再缩短第 k 个子匹配，考虑之前的匹配 */
			fc_k--;
		}
	}

	/* 所有可能性已耗尽 */
	FREE(fc_endpts);

	/*
	 * 现在考虑通过使用零重复来匹配零长度字符串的可能性。
	 */
	if (fc_t->min == 0 && fc_begin == fc_end)
	{
		MDEBUG(("%d: allowing zero matches\n", fc_t->id));
		return REG_OKAY;
	}

	MDEBUG(("%d: failed\n", fc_t->id));
	return REG_NOMATCH;
}

/*
 * creviterdissect - 解析迭代节点的匹配，优先考虑最短
 */
static int						/* regexec 返回代码 */
creviterdissect(struct vars *v,
				struct subre *fc_t,
				chr *fc_begin,		/* 相关子字符串的开始 */
				chr *fc_end)		/* 结束部分 */
{
	struct dfa *fc_d;
	chr		  **fc_endpts;
	chr		   *fc_limit;
	int			fc_min_matches;
	size_t		fc_max_matches;
	int			fc_nverified;
	int			fc_k;
	int			fc_i;
	int			fc_er;

	assert(fc_t->op == '*');
	assert(fc_t->child != NULL && fc_t->child->cnfa.nstates > 0);
	assert(fc_t->child->flags & SHORTER);
	assert(fc_begin <= fc_end);

	MDEBUG(("%d: creviterdissect %ld-%ld\n", fc_t->id, LOFF(fc_begin), LOFF(fc_end)));

	/*
	 * 如果允许零个匹配，并且目标字符串为空，则直接宣布胜利。
	 * 另一方面，如果目标字符串不为空，则零匹配不能工作，
	 * 因此我们假装最小值为 1。
	 */
	fc_min_matches = fc_t->min;
	if (fc_min_matches <= 0)
	{
		if (fc_begin == fc_end)
		{
			MDEBUG(("%d: allowing zero matches\n", fc_t->id));
			return REG_OKAY;
		}
		fc_min_matches = 1;
	}

	/*
	 * 我们需要工作区来跟踪每个子匹配的端点。通常情况下，
	 * 我们只考虑非零长度的子匹配，因此最多可以有 end-begin 个。
	 * 不过，如果 min 大于该值，我们还将考虑零长度的子匹配以找到足够的匹配。
	 *
	 * 为了方便，endpts[0] 包含“开始”指针，我们将
	 * 子匹配端点存储在 endpts[1..max_matches] 中。
	 */
	fc_max_matches = fc_end - fc_begin;
	if (fc_max_matches > fc_t->max && fc_t->max != DUPINF)
		fc_max_matches = fc_t->max;
	if (fc_max_matches < fc_min_matches)
		fc_max_matches = fc_min_matches;
	fc_endpts = (chr **) MALLOC((fc_max_matches + 1) * sizeof(chr *));
	if (fc_endpts == NULL)
		return REG_ESPACE;
	fc_endpts[0] = fc_begin;

	fc_d = getsubdfa(v, fc_t->child);
	if (ISERR())
	{
		FREE(fc_endpts);
		return v->err;
	}

	/*
	 * 我们的策略是首先找到一组根据子节点的 DFA
	 * 有效的子匹配端点，然后递归解析每个子匹配以确认有效性。
	 * 如果任何有效性检查失败，回溯该子匹配并重试。
	 * 当我们下次进行有效性检查时，我们不必重新检查
	 * 任何我们没有移动端点的成功验证的子匹配。nverified 记住
	 * 当前已知的有效子匹配数量。
	 */

	/* 初始化考虑第一个子匹配 */
	fc_nverified = 0;
	fc_k = 1;
	fc_limit = fc_begin;

	/* 迭代直到满意或失败 */
	while (fc_k > 0)
	{
		/* 除非必要，否则不允许零长度匹配 */
		if (fc_limit == fc_endpts[fc_k - 1] &&
			fc_limit != fc_end &&
			(fc_k >= fc_min_matches || fc_min_matches - fc_k < fc_end - fc_limit))
			fc_limit++;

		/* 如果这是最后一个允许的子匹配，它必须到达结尾 */
		if (fc_k >= fc_max_matches)
			fc_limit = fc_end;

		/* 尝试为第 k 个子匹配找到端点 */
		fc_endpts[fc_k] = shortest(v, fc_d, fc_endpts[fc_k - 1], fc_limit, fc_end,
							 (chr **) NULL, (int *) NULL);
		if (ISERR())
		{
			FREE(fc_endpts);
			return v->err;
		}
		if (fc_endpts[fc_k] == NULL)
		{
			/* 无法匹配，因此查看我们是否可以延长上一个匹配 */
			fc_k--;
			goto backtrack;
		}
		MDEBUG(("%d: working endpoint %d: %ld\n",
				fc_t->id, fc_k, LOFF(fc_endpts[fc_k])));

		/* 第 k 个子匹配不再被视为已验证 */
		if (fc_nverified >= fc_k)
			fc_nverified = fc_k - 1;

		if (fc_endpts[fc_k] != fc_end)
		{
			/* 还没有到达结尾，如果允许，则尝试另一个迭代 */
			if (fc_k >= fc_max_matches)
			{
				/* 必须尝试延长某个先前的匹配 */
				fc_k--;
				goto backtrack;
			}

			fc_k++;
			fc_limit = fc_endpts[fc_k - 1];
			continue;
		}

		/*
		 * 我们已确定一种将字符串划分为 k 个子匹配的方式，
		 * 根据子 DFA 截至目前为止是有效的。如果 k 是允许的匹配数量，
		 * 开始回归的慢部分：递归以验证每个子匹配。
		 * 我们始终有 k <= max_matches，无需检查。
		 */
		if (fc_k < fc_min_matches)
			goto backtrack;

		MDEBUG(("%d: verifying %d..%d\n", fc_t->id, fc_nverified + 1, fc_k));

		for (fc_i = fc_nverified + 1; fc_i <= fc_k; fc_i++)
		{
			/* 从非最后一个迭代中删除任何匹配数据 */
			zaptreesubs(v, fc_t->child);
			fc_er = cdissect(v, fc_t->child, fc_endpts[fc_i - 1], fc_endpts[fc_i]);
			if (fc_er == REG_OKAY)
			{
				fc_nverified = fc_i;
				continue;
			}
			if (fc_er == REG_NOMATCH)
				break;
			/* 哎呀，出现问题了 */
			FREE(fc_endpts);
			return fc_er;
		}

		if (fc_i > fc_k)
		{
			/* 满意 */
			MDEBUG(("%d: successful\n", fc_t->id));
			FREE(fc_endpts);
			return REG_OKAY;
		}

		/* 第 i 个匹配未能验证，因此回溯它 */
		fc_k = fc_i;

backtrack:

		/*
		 * 必须考虑第 k 个子匹配的更长版本。
		 */
		while (fc_k > 0)
		{
			if (fc_endpts[fc_k] < fc_end)
			{
				fc_limit = fc_endpts[fc_k] + 1;
				/* 跳出回溯循环，继续外部循环 */
				break;
			}
			/* 无法再延长第 k 个子匹配，考虑之前的匹配 */
			fc_k--;
		}
	}

	/* 所有可能性已耗尽 */
	MDEBUG(("%d: failed\n", fc_t->id));
	FREE(fc_endpts);
	return REG_NOMATCH;
}



#include "rege_dfa.c"
